package fun.coding.leetcode;

public class RemoveDuplicatesFromSortedListII {

	public static void main(String[] args) {
		RemoveDuplicatesFromSortedListII instance = new RemoveDuplicatesFromSortedListII();

		int[] a1 = {1, 2, 3, 3, 4, 4, 5};
		ListNode l1 = LeetCodeHelpers.buildLinkedList(a1);
		ListNode l1Res = instance.deleteDuplicates(l1);
		// LeetCodeHelpers.printList(l1Res);

		int[] a2 = {1, 1, 1, 2, 3};
		ListNode l2 = LeetCodeHelpers.buildLinkedList(a2);
		ListNode l2Res = instance.deleteDuplicates(l2);
		// LeetCodeHelpers.printList(l2Res);


		int[] a3 = {1, 1, 1, 2, 3, 3, 4, 4};
		ListNode l3 = LeetCodeHelpers.buildLinkedList(a3);
		ListNode l3Res = instance.deleteDuplicates(l3);
		LeetCodeHelpers.printList(l3Res);

	}

	// Given 1->2->3->3->4->4->5, return 1->2->5.
	// Given 1->1->1->2->3, return 2->3.
	// Didn't use dummy node, that's why for head case need to do it specially. 
	public ListNode deleteDuplicatesHardImplementation(ListNode head) {
		ListNode pre = null;
		ListNode cur = head;
		ListNode next = null;

		while (cur != null) {
			next = cur.next;
			boolean isDup = false;

			while (next != null && cur.val == next.val) {
				next = next.next;
				isDup = true;
			}

			if (isDup) {
				if (pre == null) {
					head = next;
				} else {
					pre.next = next;
				}
			} else {
				pre = cur;
			}

			cur = next;
		}

		return head;
	}

	// Using a dummy node as a safeguard will make things easier.
	// this is a common technique for linkedList problems

	public ListNode deleteDuplicates(ListNode head) {
		if (head == null || head.next == null) return head;
		
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		
		ListNode pre = dummy;
		ListNode cur = head;
		
		while (cur != null) {
			ListNode fast = cur.next;
			boolean isDup = false;
			
			while (fast != null && fast.val == cur.val) {
				fast = fast.next;
				isDup = true;
			}
			
			if (isDup) {
				pre.next = fast;
				cur = fast;
			} else {
				pre = cur;
				cur = cur.next;
			}
		}
		
		
		return dummy.next;
	}
}
